﻿#include<iostream>
using namespace std;

const int N = 1e6 + 10;//定义数组大小
int q[N]; //定义一个大小为N的数组
int n; //代表你输入几个数字

//参数1：数组名，参数2：数组首，参数三：数组尾
void quick_sort(int q[], int l, int r) //整个区间
{					     //	 0      4 
	/*if(l >= r) 包含if(l == r),这也可以写if(l == r)*/
	if (l >= r)//如果数组只有一个数时直接返回
	{
		return;
	}
	int x = q[l];//选取一个分界值

	int i = l - 1, j = r + 1; //指向首位的外侧，防止泄露

	while (i < j) //( -1 < 5 )
	{
		do i++;
		while (q[i] < x);  //先i++，再判断条件
		do j--;
		while (q[j] > x);  //先j++，再判断条件

		if (i < j)
		{
			//交换两个数
			int temp = q[i];
			q[i] = q[j];
			q[j] = temp;
		}
	}

	//递归，慢慢理解
	quick_sort(q, l, j);//左边区间
	quick_sort(q, j + 1, r);//右边区间
}
int main()
{
	cout << "您准备几个数字进行排序：";
	cin >> n;  //举例：输入5
	cout << endl;

	cout << "请输入" << n << "个需要排序的数字，用空格隔开" << endl;
	for (int i = 0; i < n; i++)
	{
		//从数组下标为0开始存储 q[0]-q[n-1]
		cin >> q[i];
	}
	//参数1：数组名，参数2：数组首，参数三：数组尾
	quick_sort(q, 0, n - 1);

	cout << "排序后的的数字入下:" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << q[i] << " ";
	}
	cout << endl;
	system("pause");
	return 0;
};